package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/14 11:21
 * @description:剑指offer-46 把数字翻译成字符串
 *
 * dp[i]:表示前i个数字的翻译方法可能个数
 * num = X1X2X3....Xi-1Xi...Xn-1Xn
 * 例如:12258 = X1X2X3X4X5
 * 设 X1X2...Xi-2的翻译方案数量为f(i-2)
 * 设X1X2...X
 */

public class Translation {

    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int num = sr.nextInt();
        System.out.println(new Tracnslation_Solution().translateNum(num));
        System.out.println(new Tracnslation_Solution().translateNum2(num));
    }
}

class Tracnslation_Solution{

    public int translateNum(int num){
        String s = String.valueOf(num); //int 转换成string
        //初始化 dp[-1]  = 0
        int p = 0, q = 0, r = 1;
        for(int i = 0; i < s.length();i++){
            p = q;  // q从上一轮的i-1,变为这一轮的i-2 --->p(i-2)
            q = r; //res为上一轮的i,赋值到这一轮的i-1 ---->q(i-1)
            r = 0; //r重置
            r += q; //r开始累计了，当前先加上i-1
            //下面开始尝试，是否要再累加 i-2
            if(i ==0){
                continue;
            }
            String sub = s.substring(i-1,i+1);//不包含i+1,也就是i-1 i
            if(sub.compareTo("25") <= 0 && sub.compareTo("10") >=0){
                r += p;
            }
        }
        return r;
    }
    public int translateNum2(int num){
        String s = String.valueOf(num);
        int n = s.length();
        int [] dp = new int[n+1];
        dp[0] = 1;
        for(int i =1;i<=n;i++){
            dp[i] = dp[i-1];  //单独翻译
            if(i>1){
                int t = (s.charAt(i-2) - '0')*10+s.charAt(i-1) - '0';
                if(t >=10 && t<=25){
                    dp[i] += dp[i-2];   //将dp[i]和dp[i-1]组合翻译
                }
            }
        }
        return dp[n];
    }
}
